package main

//#link: https://leetcode-cn.com/problems/cousins-in-binary-tree/
import (
	"fmt"
	. "whoops/leetcode/common"
)

func main() {

}

//深度相同，父节点不同
func isCousins(root *TreeNode, x int, y int) bool {
	height1, parent1 := getTreeHeightAndRoot(root.Left, root.Val, x)
	height2, parent2 := getTreeHeightAndRoot(root.Right, root.Val, y)
	fmt.Println(height1, height2, parent1, parent2)
	if height1 != height2 {
		return false
	} else {
		if parent1 == parent2 {
			return false
		}
	}
	return true
}

//获取树的深度和根节点 树的深度 和父节点的值
func getTreeHeightAndRoot(root *TreeNode, val, parent int) (int, int) {
	result := 0
	queue := new(Queue)
	queue.poll(root)
	for len(queue.Nums) > 0 {
		num := len(queue.Nums)
		result++
		parent = queue.Nums[0].Val
		for num > 0 {
			node := queue.pop()
			if node.Val == val {
				return result, parent
			}
			if node.Left != nil {
				queue.poll(node.Left)
			}
			if node.Right != nil {
				queue.poll(node.Right)
			}
			num--
		}
	}
	return result, parent
}

type Queue struct {
	Nums []*TreeNode
}

func (q *Queue) poll(node *TreeNode) {
	if len(q.Nums) == 0 {
		q.Nums = make([]*TreeNode, 0)
	}
	q.Nums = append(q.Nums, node)
}

func (q *Queue) pop() *TreeNode {
	node := q.Nums[0]
	q.Nums = q.Nums[1:]
	return node
}
